
using System;

using System.Collections.Generic;
using UnityEngine;

public class Solution : MonoBehaviour
{

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }
    void Start()
    {
        int[] nums = { 5, 5, 6, 6, 7, 8, 1, 2, 3, 4, 5 };
        //Debug.Log(MinArray(nums));

    }
    // public int[] LevelOrder(TreeNode root)
    // {
    //     if (root==null)
    //     {
    //         return new int[0];
    //     }
    //     Queue<TreeNode> node_list = new Queue<TreeNode>();
    //     node_list.Enqueue(root);
    //     List<int> list = new List<int>();
    //     TreeNode node=new TreeNode(0);

    //     while (node_list.Count >0)
    //     {
    //          node = node_list.Dequeue();
    //          list.Add(node.val);
    //          if(node.left!=null){
    //              node_list.Enqueue(node.left);
    //          }
    //          if(node.right!=null){
    //              node_list.Enqueue(node.right);
    //          }
    //     }
    //     int[] result_list=new int[list.Count];

    //     for (int i = 0; i < =list.Count-1; i++)
    //     {
    //         result_list[i]=list[i];
    //     }       
    //     return result_list;
    // }



    ///我的思路 根据奇偶直接对不同层反序

    ///官方思路 根据奇偶和双端队列(通过linkdelist链表进行模拟) 进行插入 不用排序
    public List<LinkedList<int>> levelOrder(TreeNode root)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        List<LinkedList<int>> res = new List<LinkedList<int>>();
        if (root != null) queue.Enqueue(root);
        while (queue.Count>0)
        {
            LinkedList<int> tmp = new LinkedList<int>();
            for (int i = queue.Count; i > 0; i--)
            {
                TreeNode node = queue.Dequeue();
                if (res.Count % 2 == 0) tmp.AddLast(node.val); // 偶数层 -> 队列头部
                else tmp.AddFirst(node.val); // 奇数层 -> 队列尾部
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            res.Add(tmp);
        }
        return res;
    }

}